   public class LinkedList<T> implements ListInterface<T> {
      private Node<T> head, tail;
      private int count;
   
      public LinkedList() {
         count=0;
         head = new Node<T>(null);
         head.setNext(new Node<T>(null));
         tail = head.getNext();
      }
   
      public boolean add(T elt){
         tail.setData(elt);
         tail.setNext(new Node<T>(null));
         tail=tail.getNext();
         count++;
		return true;
      }
      
      public void addFirst(T elt){
         head.setNext(new Node<T>(elt, head.getNext()));
         count++;
      }
   
      public void addAt(T elt, int idx){  
         int i;
         Node<T> p=head;
         if (idx<0 || idx>count)
            throw new IllegalArgumentException("Out of bounds: " + idx);
         for (i=0; i<idx; i++)
            p = p.getNext();
         p.setNext(new Node<T>(elt,p.getNext()));
         count++;
      }
   
      public int find(T elt){ 
         Node<T> p = head.getNext();
         int idx = 0;
         while (p!=tail) {
            if (p.getData().equals(elt))
               return idx;
            p=p.getNext();	
            idx++;
         }	 
         return -1;
      }
   
      public boolean contains(T elt){ 
         Node<T> p = head.getNext();
         while (p!=tail) {
            if (p.getData().equals(elt))
               return true;
            p=p.getNext();	
         }
         return false;
      }
   
      public boolean isEmpty(){ 
         return count==0; }
   
      public void makeEmpty(){
         count=0;
         head.setNext(tail);
      }
   
      public void printList(){
         Node<T> p = head.getNext();
         while (p!=tail) {
            System.out.print(p + " ");
            p = p.getNext();
         }
         System.out.println();
      }
   
      public T findKth(int idx){
         int i;
         Node<T> p = head.getNext();
         if (idx<0 || idx>=count)
            throw new IllegalArgumentException("Out of bounds: "+idx);
         for (i=0; i<idx; i++)
            p=p.getNext();
         return p.getData(); 
      }
   
      public boolean remove(T elt){
         int place = find(elt);    
         return removeAt(place);  
      }
   
      public boolean removeAt(int idx){ 
         Node<T> p = head;
         if (idx<0 || idx>=count)
            return false;
         for (int i=0; i<idx; i++)
            p=p.getNext();
         p.setNext(p.getNext().getNext());
         count--;
         return true; 
      }
   
      public int size(){ 
         return count; }
   
      public Object[] toArray(){ 
         Node<T> p = head.getNext();
         Object[] newArray = new Object[count];
         int i=0;
         while (p!=tail) {
            newArray[i] = p.getData();
            ++i;
            p=p.getNext();
         }
         return newArray;  
      }

	@Override
	public void clear() {
		// TODO Auto-generated method stub
		
	}

	@Override
	public T get(int index) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public T set(int index, T element) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public void add(int index, T item) {
		// TODO Auto-generated method stub
		
	}

	@Override
	public T remove(int index) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public int indexOf(T item) {
		// TODO Auto-generated method stub
		return 0;
	}
	/*
	public void addNodeAfter(T element)
	{
		next = new Node<T>(element, next);
	}
	public void removeNodeAfter() {
		next = next.next;
	}
	public static boolean inList(Node<T> head,T target) {
		Node<T> ptr;
		for (ptr=head; (ptr!=null) && (ptr.getData()!=target); ptr = ptr.getNext())
		     ; // No loop body!
		if (ptr==null) {
			return false;
		}
		else {
			return true;
		}
	}
	
    public static void main(String[] args) {
        LinkedList<String> ll = new LinkedList<String>();
        ll.addFirst("three");
        ll.addFirst("one");
        ll.add("five");
        ll.addAt("two",1);
        ll.printList();
        if (ll.contains("five"))
           System.out.println("five is at position " 
                         + ll.find("five"));
     //if (ll.contains("goober"))
        System.out.println("goober is at position " 
                         + ll.find("goober"));
        System.out.println("at position 3 is " + ll.findKth(3));
        System.out.println("removing five? " + ll.remove("five"));
        System.out.println("removing five? " + ll.remove("five"));
        ll.printList();
        Object[] ary = ll.toArray();
			for (Object obj: ary) System.out.println(obj);
     }
     */
	
   }